/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include<iostream>
using namespace std;
#include<unordered_map>
#include<unordered_set>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*,TreeNode*> p_map;
        this->findParent(root,p_map);
        cout << "生成父节点数据" << endl;
        unordered_set<TreeNode*> p_set;
        TreeNode* cur = p;
        while(true){
            p_set.insert(cur);
            if(cur == root){
                break;
            }
            cur = p_map.find(cur)->second;
        }
        cout << "生成p节点祖宗集合" << endl;
        for(auto it = p_set.begin(); it != p_set.end(); it++){
            cout << (*it)->val << endl;
        }
        cur = q;
        while(true){
            cout << "find" << cur->val << endl;
            if(p_set.find(cur) != p_set.end()){
                cout << "find OK" << endl;
                return cur;
            }
            if(cur == root){
                break;
            }
            cur = p_map.find(cur)->second;
        }
        cout << "结束" << endl;
        return NULL;
    }
    void findParent(TreeNode* root,unordered_map<TreeNode*,TreeNode*>& p_map) {
        if(root == NULL){
            return;
        }
        if(root->right){
            p_map.insert(pair<TreeNode*,TreeNode*>(root->right,root));
        }
        if(root->left){
            p_map.insert(pair<TreeNode*,TreeNode*>(root->left,root));
        }
        findParent(root->left,p_map);
        findParent(root->right,p_map);
    }
};

class Solution2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) {
            return root;
        }
        auto left = this->lowestCommonAncestor(root->left,p,q);
        auto right = this->lowestCommonAncestor(root->right,p,q);
        if(left != NULL && right != NULL) {
            return root;
        }
        return left != NULL ? left : right;
    }
};

int main(){

}